using System;
using System.Collections.Generic;
using System.Text;

namespace CAIR.Lib
{
    public class EnergyMap
    {
        public class Node
        {
            private Node _previous;
            private Node _next;
            private Node _parent;
            private Node _above;
            private Node _bottom;
            private double _value;
            private string _id; // for debugging

            public string ID
            {
                get { return _id; }
                set { _id = value; }
            }
            public double Value
            {
                get { return _value; }
                set { _value = value; }
            }
            public Node Bottom
            {
                get { return _bottom; }
                set { _bottom = value; }
            }
            public Node Above
            {
                get { return _above; }
                set { _above = value; }
            }
            public Node Parent
            {
                get { return _parent; }
                set { _parent = value; }
            }
            public Node Next
            {
                get { return _next; }
                set { _next = value; }
            }
            public Node Previous
            {
                get { return _previous; }
                set { _previous = value; }
            }

            public Node()
            {
            }
            public Node(Node previous, Node next)
            {
                _previous = previous;
                _next = next;
            }
            public Node(string id)
            {
                _id = id;
            }
            public override string ToString()
            {
                return ID;
            }
        }

        private Node[] _rows;
        public Node FirstNode
        {
            get { return _rows[0]; }
        }
        public Node[] Rows
        {
            get { return _rows; }
        }
        /// <summary>
        /// Initializes a grid with the given diminsions
        /// </summary>
        /// <param name="height"></param>
        /// <param name="width"></param>
        public EnergyMap(int height, int width)
        {
            _rows = new Node[height];

            // Initialize first row
            Node firstRowIter = _rows[0] = new Node("0, 0");
            for (int j = 0; j < width - 1; j++)
            {
                firstRowIter.Next = new Node("0, " + j.ToString());
                firstRowIter.Next.Previous = firstRowIter;
                firstRowIter = firstRowIter.Next;
            }
            // Initialize first column
            firstRowIter = _rows[0];
            for (int i = 1; i < height; i++)
            {
                firstRowIter.Bottom = new Node(i.ToString() + ", 0");
                firstRowIter.Bottom.Above = firstRowIter;
                firstRowIter = firstRowIter.Bottom;
                _rows[i] = firstRowIter;
            }
            // Initialize the rest of the grid
            for (int i = 1; i < height; i++)
            {
                Node current = _rows[i];// = new Node();
                current.Next = new Node(i.ToString() + ", 1");
                current.Next.Previous = current;
                current = current.Next;
                for (int j = 1; j < width; j++)
                {
                    if (j < width - 1)
                    {
                        current.Next = new Node(i.ToString() + ", " + (j + 1).ToString());
                        current.Next.Previous = current;
                    }
                    current.Above = current.Previous.Above.Next;
                    current.Above.Bottom = current;
                    current = current.Next;
                }
            }
        }

        internal int[] Extract(Node minInd, int ind)
        {
            int[] result = new int[_rows.Length];
            result[_rows.Length - 1] = ind;
            
            // previous is used to reverse the direction
            Node previous = null;
            Node n = minInd;
            for (int i = _rows.Length - 1; n.Above != null; i--)
            {
                if (n.Above.Previous != null && n.Parent == n.Above.Previous)
                {
                    result[i - 1] = result[i] - 1;
                }
                else if (n.Above != null && n.Parent == n.Above)
                {
                    result[i - 1] = result[i];
                }
                else if (n.Above.Next != null && n.Parent == n.Above.Next)
                {
                    result[i - 1] = result[i] + 1;
                }
                // Reverse path direction
                Node temp = n.Parent;
                n.Parent = previous;
                previous = n;
                n = temp;
            }
            n.Parent = previous;
            UpdateOptimalSeams(n);
            return result;
        }

        private void UpdateOptimalSeams(Node node)
        {
            // Traverse the path and update pointers/values
            while (true)
            {
                // Check if this is the last row
                if (node.Parent == null)
                {
                    // Update horizontally
                    if (node.Previous != null)
                        node.Previous.Next = node.Next;
                    if (node.Next != null)
                        node.Next.Previous = node.Previous;
                    break;
                }

                // Update vertically
                if (node.Parent == node.Bottom)
                    UpdateVertical(node);
                else if (node.Bottom.Previous != null && node.Parent == node.Bottom.Previous)
                    UpdateRightDiagonal(node);
                else if (node.Bottom.Next != null && node.Parent == node.Bottom.Next)
                    UpdateLeftDiagonal(node);

                // iterate
                node = node.Parent;
            }
        }

        private void UpdateLeftDiagonal(Node node)
        {
            Node parent;
            // Update bottom node
            if (node.Bottom != null)
            {
                double min = GetMinCenter(node, out parent);
                node.Bottom.Value = node.Bottom.Value - min;
            }
            if (node.Bottom.Previous != null)
            {
                double min = GetMinRight(node, out parent);
                node.Bottom.Previous.Value = node.Bottom.Previous.Value - min;
            }

            // remove the current node from the row and update the affected nodes' values
            double minForBottom, minForBottomLeft;
            if (node.Previous != null)
            {
                node.Previous.Next = node.Next;
                minForBottomLeft = GetMinCenter(node.Previous, out parent);
                node.Bottom.Previous.Value = minForBottomLeft + node.Bottom.Previous.Value;
                node.Bottom.Previous.Parent = parent;
            }
            if (node.Next != null)
            {
                node.Next.Previous = node.Previous;
                minForBottom = GetMinCenter(node.Next, out parent);
                node.Bottom.Value = minForBottom + node.Bottom.Value;
                node.Bottom.Parent = parent;

                // Update vertical links
                node.Next.Bottom = node.Bottom;
                node.Bottom.Above = node.Next;
            }
        }

        private void UpdateRightDiagonal(Node node)
        {
            Node parent;
            // Update bottom node
            if (node.Bottom != null)
            {
                double min = GetMinCenter(node, out parent);
                node.Bottom.Value = node.Bottom.Value - min;
            }
            if (node.Bottom.Next != null)
            {
                double min = GetMinRight(node, out parent);
                node.Bottom.Next.Value = node.Bottom.Next.Value - min;
            }

            // remove the current node from the row and update the affected nodes' values
            double minForBottom, minForBottomRight;
            if (node.Previous != null)
            {
                node.Previous.Next = node.Next;
                minForBottom = GetMinCenter(node.Previous, out parent);
                node.Bottom.Value = minForBottom + node.Bottom.Value;
                node.Bottom.Parent = parent;

                // Update vertical links
                node.Previous.Bottom = node.Bottom;
                node.Bottom.Above = node.Previous;
            }
            if (node.Next != null)
            {
                node.Next.Previous = node.Previous;
                minForBottomRight = GetMinCenter(node.Next, out parent);
                node.Bottom.Next.Value = minForBottomRight + node.Bottom.Next.Value;
                node.Bottom.Next.Parent = parent;
            }
        }

        private void UpdateVertical(Node node)
        {
            Node parent;
            // Update bottom left node
            if (node.Bottom.Previous != null)
            {
                double min = GetMinLeft(node, out parent);
                node.Bottom.Previous.Value = node.Bottom.Previous.Value - min;
            }
            if (node.Bottom.Next != null)
            {
                double min = GetMinRight(node, out parent);
                node.Bottom.Next.Value = node.Bottom.Next.Value - min;
            }

            // remove the current node from the row and update the affected nodes' values
            double minForBottomLeft, minForBottomRight;
            if (node.Previous != null)
            {
                node.Previous.Next = node.Next;
                minForBottomLeft = GetMinCenter(node.Previous, out parent);
                node.Bottom.Previous.Value = minForBottomLeft + node.Bottom.Previous.Value;
                node.Bottom.Previous.Parent = parent;
            }
            if (node.Next != null)
            {
                node.Next.Previous = node.Previous;
                minForBottomRight = GetMinCenter(node.Next, out parent);
                node.Bottom.Next.Value = minForBottomRight + node.Bottom.Next.Value;
                node.Bottom.Next.Parent = parent;
            }
        }

        /// <summary>
        /// Gets the minimum value of 3 nodes to the left of the given nodes
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private double GetMinLeft(Node node, out Node parent)
        {
            double min = node.Value;
            parent = node;
            if (node.Previous != null && node.Previous.Value < min)
            {
                min = node.Previous.Value;
                parent = node.Previous;
            }
            if (node.Previous != null && node.Previous.Previous != null && node.Previous.Previous.Value < min)
            {
                min = node.Previous.Previous.Value;
                parent = node.Previous.Previous;
            }
            return min;
        }
        /// <summary>
        /// Gets the minimum value of 3 nodes assuming the current one is on the center
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private double GetMinCenter(Node node, out Node parent)
        {
            double min = node.Value;
            parent = node;
            if (node.Previous != null && node.Previous.Value < min)
            {
                min = node.Previous.Value;
                parent = node.Previous;
            }
            if (node.Next != null && node.Next.Value < min)
            {
                min = node.Next.Value;
                parent = node.Next;
            }
            return min;
        }
        /// <summary>
        /// Gets the minimum value of 3 nodes to the right of the given node
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private double GetMinRight(Node node, out Node parent)
        {
            double min = node.Value;
            parent = node;
            if (node.Next != null && node.Next.Value < min)
            {
                min = node.Next.Value;
                parent = node.Next;
            }
            if (node.Next != null && node.Next.Next != null && node.Next.Next.Value < min)
            {
                min = node.Next.Next.Value;
                parent = node.Next.Next;
            }
            return min;
        }
    }
}
